#include<iostream>
#include <iterator>
using namespace std;

//class Solution {
//public:
//    /**
//     * �����е����������������������Ѿ�ָ���������޸ģ�ֱ�ӷ��ط����涨��ֵ����
//     *
//     * ����������֮��
//     * @param s string�ַ��� ��ʾ��һ������
//     * @param t string�ַ��� ��ʾ�ڶ�������
//     * @return string�ַ���
//     */
//    string solve(string s, string t) {
//        if (s == "" && t != "") {
//            return t;
//        }
//        else if (s != "" && t == "") {
//            return s;
//        }
//        else {
//            string ret;
//            int jinwei = 0;
//            int i = s.size() - 1, j = t.size() - 1;
//            while (i >= 0 && j >= 0) {
//                int sum = (s[i] - '0') + (t[j] - '0');
//                if (jinwei > 0)
//                    sum += jinwei;
//                if (sum >= 10)
//                    jinwei++;
//                i--;
//                j--;
//                ret.push_back(sum % 10 + '0');
//            }
//            while (i >= 0)
//            {
//                int sum = s[i] - '0';
//                if (jinwei > 0)
//                {
//                    sum += jinwei;
//                    jinwei = 0;
//                }
//                if (sum >= 10)
//                    jinwei++;
//                i--;
//                ret.push_back(sum % 10 + '0');
//            }
//            while (j >= 0)
//            {
//                int sum = t[j] - '0';
//                if (jinwei > 0)
//                {
//                    sum += jinwei;
//                    jinwei = 0;
//                }
//                if (sum >= 10)
//                    jinwei++;
//                j--;
//                ret.push_back(sum % 10 + '0');
//            }
//            if (jinwei > 0)
//            {
//                ret.push_back(jinwei + '0');
//            }
//            reverse(ret.begin(), ret.end());
//            return ret;
//        }
//    }
//};


//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(nullptr) {}
//};
 
#include <type_traits>
//class Solution {
//public:
//    /**
//     * �����е����������������������Ѿ�ָ���������޸ģ�ֱ�ӷ��ط����涨��ֵ����
//     *
//     *
//     * @param head1 ListNode��
//     * @param head2 ListNode��
//     * @return ListNode��
//     */
//    ListNode* addInList(ListNode* head1, ListNode* head2) {
//        int len1 = 0;
//        int len2 = 0;
//        ListNode* now1 = head1;
//        ListNode* now2 = head2;
//        while (now1) {
//            now1 = now1->next;
//            len1++;
//        }
//        while (now2) {
//            now2 = now2->next;
//            len2++;
//        }
//        int up = 0;
//        ListNode* ret = new ListNode(0);
//
//        ListNode* tmp = ret;
//        while (len1 > 0 && len2 > 0) {
//            int sum = 0;
//            now1 = head1;
//            now2 = head2;
//            int nowlen1 = len1, nowlen2 = len2;
//            while (--nowlen1) now1 = now1->next;
//            while (--nowlen2) now2 = now2->next;
//            sum = now1->val + now2->val;
//            if (up > 0) {
//                sum += up;
//                up = 0;
//            }
//            if (sum >= 10)
//                up++;
//
//            ListNode* newNode = new ListNode(sum % 10);
//            tmp->next = newNode;
//            tmp = newNode;
//
//            len1--;
//            len2--;
//        }
//        while (len1 > 0)
//        {
//            now1 = head1;
//            int nowlen1 = len1;
//            while (--nowlen1)   now1 = now1->next;
//            int sum = now1->val;
//            if (up > 0)
//            {
//                sum += up;
//                up = 0;
//            }
//            if (sum >= 10)
//                up++;
//            ListNode* newNode = new ListNode(sum % 10);
//            tmp->next = newNode;
//            tmp = newNode;
//            len1--;
//        }
//        while (len2 > 0)
//        {
//            now2 = head2;
//            int nowlen2 = len2;
//            while (--nowlen2)   now2 = now2->next;
//            int sum = now2->val;
//            if (up > 0)
//            {
//                sum += up;
//                up = 0;
//            }
//            if (sum >= 10)
//                up++;
//            ListNode* newNode = new ListNode(sum % 10);
//            tmp->next = newNode;
//            tmp = newNode;
//            len2--;
//        }
//        if (up > 0)
//        {
//            ListNode* newNode = new ListNode(up);
//            tmp->next = newNode;
//            tmp = newNode;
//        }
//
//        ret = ret->next;
//        ListNode* old = nullptr;
//        while (ret != tmp)
//        {
//            ListNode* now = ret;
//
//            ret = ret->next;
//            now->next = old;
//            old = now;
//        }
//        ret->next = old;
//        return ret;
//    }
//};
//int main()
//{
//    ListNode* head1 = new ListNode(0);
//    ListNode* h1 = new ListNode(9);
//    ListNode* h2 = new ListNode(3);
//    ListNode* h3 = new ListNode(7);
//    ListNode* head2 = new ListNode(0);
//    ListNode* h4 = new ListNode(6);
//    ListNode* h5 = new ListNode(3);
//    head1->next = h1;
//    h1->next = h2;
//    h2->next = h3;
//    h3->next = nullptr;
//    head2->next = h4;
//    h4->next = h5;
//    h5->next = nullptr;
//    Solution s;
//    s.addInList(head1->next, head2->next);
//}

//#include<algorithm>
//#include<string>
//#include<vector>
//class Solution {
//public:
//    /**
//     * �����е����������������������Ѿ�ָ���������޸ģ�ֱ�ӷ��ط����涨��ֵ����
//     *
//     *
//     * @param s string�ַ��� ��һ������
//     * @param t string�ַ��� �ڶ�������
//     * @return string�ַ���
//     */
//    string solveadd(string s, string t) {
//        if (s == "" && t != "") {
//            return t;
//        }
//        else if (s != "" && t == "") {
//            return s;
//        }
//        else {
//            string ret;
//            int jinwei = 0;
//            int i = s.size() - 1, j = t.size() - 1;
//            while (i >= 0 && j >= 0) {
//                int sum = (s[i] - '0') + (t[j] - '0');
//                if (jinwei > 0)
//                {
//                    sum += jinwei;
//                    jinwei = 0;
//                }
//                if (sum >= 10)
//                    jinwei++;
//                i--;
//                j--;
//                ret.push_back(sum % 10 + '0');
//            }
//            while (i >= 0)
//            {
//                int sum = s[i] - '0';
//                if (jinwei > 0)
//                {
//                    sum += jinwei;
//                    jinwei = 0;
//                }
//                if (sum >= 10)
//                    jinwei++;
//                i--;
//                ret.push_back(sum % 10 + '0');
//            }
//            while (j >= 0)
//            {
//                int sum = t[j] - '0';
//                if (jinwei > 0)
//                {
//                    sum += jinwei;
//                    jinwei = 0;
//                }
//                if (sum >= 10)
//                    jinwei++;
//                j--;
//                ret.push_back(sum % 10 + '0');
//            }
//            if (jinwei > 0)
//            {
//                ret.push_back(jinwei + '0');
//            }
//            reverse(ret.begin(), ret.end());
//            return ret;
//        }
//    }
//    string solve(string s, string t) {
//        if (s == "0" || t == "0")   return "0";
//        int ssize = s.size();
//        int tsize = t.size();
//        int jinwei = 0;
//
//        int sum = 0;
//        int count = 0;
//        vector<string> retnum;
//        for (int i = ssize - 1; i >= 0; i--)
//        {
//            string tmp;
//            int tmpcount = count;
//            for (int j = tsize - 1; j >= 0; j--)
//            {
//                int num = (s[i] - '0') * (t[j] - '0');
//                if (jinwei > 0)
//                {
//                    num += jinwei;
//                    jinwei = 0;
//                }
//                if (num >= 10)
//                    jinwei = num / 10;
//
//                while (tmpcount > 0)
//                {
//                    tmp.push_back('0');
//                    tmpcount--;
//                }
//                tmp.push_back(num % 10 + '0');
//            }
//            if (jinwei > 0)
//            {
//                tmp.push_back(jinwei+'0');
//                jinwei = 0;
//            }
//            reverse(tmp.begin(), tmp.end());
//            // sum += stoi(tmp.c_str());
//            retnum.push_back(tmp);
//            count++;
//        }
//        string ret;
//        for (auto& e : retnum)
//        {
//            ret = solveadd(ret, e);
//        }
//
//        return ret;
//    }
//};
//
//int main()
//{
//    Solution s;
//    cout<<s.solve("733064366", "459309139");
//    return 0;
//}



//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int x = n;
//    vector<string> v;
//    while (x--)
//    {
//        string tmp;
//        cin >> tmp;
//        v.push_back(tmp);
//    }
//    //dp[i][j]����i,j��β����߷���
//    vector<vector<int>> dp(n + 1, vector<int>(m + 1));
//    dp[0][1] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (v[i - 1][j - 1] == 'l')
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 4;
//            else if (v[i - 1][j - 1] == 'o')
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 3;
//            else if (v[i - 1][j - 1] == 'v')
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 2;
//            else if (v[i - 1][j - 1] == 'e')
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + 1;
//            else
//                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//        }
//    }
//    cout << dp[n][m];
//    return 0;
//}
//// 64 λ������� printf("%lld")

//#include <iostream>
//#include <vector>
//#include <algorithm>
//#include <set>
//using namespace std;
//class Solution {
//public:
//    /**
//     * �����е����������������������Ѿ�ָ���������޸ģ�ֱ�ӷ��ط����涨��ֵ����
//     *
//     * max increasing subsequence
//     * @param arr int����vector the array
//     * @return int����
//     */
//    int MLS(vector<int>& arr) {
//        set<int> s(arr.begin(), arr.end());
//        int maxc = 0;
//        int count = 1;
//        set<int>::iterator it = s.begin();
//        set<int>::iterator nit = s.begin();
//        nit++;
//        while (nit != s.end())
//        {
//            if (*nit - *it == 1)
//            {
//                count++;
//            }
//            else {
//                maxc = max(count, maxc);
//                count = 1;
//            }
//            it++;
//            nit++;
//        }
//        maxc = max(count, maxc);
//        return maxc;
//    }
//};
//
//int main()
//{
//    vector<int> v = { 7,8,2,6,1,1,7,2,4,3,4,7,5,6,8,2 };
//    Solution s;
//    cout<<s.MLS(v);
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//class Solution {
//public:
//    /**
//     * �����е����������������������Ѿ�ָ���������޸ģ�ֱ�ӷ��ط����涨��ֵ����
//     *
//     *
//     * @param numbers int����vector
//     * @return bool������
//     */
//    bool IsContinuous(vector<int>& numbers) {
//        sort(numbers.begin(), numbers.end());
//        int count0 = 0;
//        for (int i = 1; i < numbers.size(); i++)
//        {
//            if (numbers[i - 1] == 0)
//            {
//                count0++;
//            }
//            else
//            {
//                int sub = numbers[i] - numbers[i - 1] - 1;
//                if (sub < 0)    return false;
//                count0 -= sub;
//                if (count0 < 0)
//                    return false;
//            }
//        }
//        return true;
//    } 
//};
//
//
//int main()
//{
//    vector<int> v = { 6,0,2,0,4 };
//    Solution s;
//    cout<<s.IsContinuous(v);
//}
#include <iostream>
#include <vector>
//class Solution {
//public:
//    vector<int> searchRange(vector<int>& nums, int target) {
//        if (nums.size() == 0)
//            return { -1,-1 };
//        int left = 0, right = nums.size() - 1;
//
//        // 查找左端点
//        int begin = 0;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] < target)
//                left = mid + 1;
//            else
//                right = mid;
//        }
//        if (nums[left] != target)
//            return { -1,-1 };
//        else
//            begin = left;//记录左端点
//
//        // 查找右端点
//        right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] > target)
//                right = mid - 1;
//            else
//                left = mid;
//        }
//        return { begin,right };
//    }
//};

////查找左端点的模板
//while (left < right)
//{
//    int mid = left + (right - left) / 2;
//    if (...) left = mid + 1;
//    else right = mid;
//}
//
////查找右端点的模板
//while (left < right)
//{
//    int mid = left + (right - left + 1) / 2;
//    if (...) right = mid - 1;
//    else left = mid;
//}
//class Solution {
//public:
//    int mySqrt(int x) {
//        if (x < 1) return 0;
//
//        int left = 1, right = x;
//
//        while (left < right)
//        {
//            long long mid = left + (right - left + 1) / 2;
//            if (mid * mid <= x) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};

//class Solution
//{
//	public int searchInsert(int[] nums, int target)
//	{
//		int left = 0, right = nums.length - 1;
//		while (left < right)
//		{
//			int mid = left + (right - left) / 2;
//			if (nums[mid] < target) left = mid + 1;
//			else right = mid;
//		}
//		// 特判⼀下第三种情况
//		if (nums[right] < target) return right + 1;
//		return right;
//	}
//}
//class Solution {
//public:
//    int peakIndexInMountainArray(vector<int>& arr) {
//        int left = 0, right = arr.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (arr[mid] < arr[mid + 1]) left = mid + 1;
//            else right = mid;
//        }
//        return left;
//    }
//};

//class Solution {
//public:
//    int findPeakElement(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left + 1) / 2;
//            if (nums[mid] > nums[mid - 1]) left = mid;
//            else right = mid - 1;
//        }
//        return left;
//    }
//};

//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int left = 0, right = nums.size() - 1;
//        int x = nums[right];
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (nums[mid] > x) left = mid + 1;
//            else right = mid;
//        }
//        return nums[left];
//    }
//};

//class Solution {
//public:
//    int takeAttendance(vector<int>& records) {
//        int left = 0, right = records.size() - 1;
//        while (left < right)
//        {
//            int mid = left + (right - left) / 2;
//            if (records[mid] == mid) left = mid + 1;
//            else right = mid;
//        }
//        return records[left] == left ? left + 1 : left;
//    }
//};

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    // 1.输入数据
//    int n, q;
//    cin >> n >> q;
//    vector<int> arr(n + 1);
//    for (int i = 1; i <= n; i++) cin >> arr[i];
//
//    // 2.预处理出来一个前缀和数组
//    vector<long long> dp(n + 1);
//    for (int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
//
//    // 3.使用前缀和数组
//    int l, r;
//    while (q--)
//    {
//        cin >> l >> r;
//        cout << dp[r] - dp[l - 1] << endl;
//    }
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    // 1.输入数据
//    int n, m, q;
//    cin >> n >> m >> q;
//    vector<vector<int>> arr(n + 1, vector<int>(m + 1));
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> arr[i][j];
//
//    // 2.预处理前缀和矩阵
//    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1));
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
//        }
//    }
//
//    // 3.使用前缀和矩阵
//    int x1, y1, x2, y2;
//    while (q--)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int size = nums.size();
//        vector<int> f(size);
//        vector<int> g(size);
//
//        for (int i = 1; i < size; i++)
//            f[i] = f[i - 1] + nums[i - 1];
//        for (int i = size - 2; i >= 0; i--)
//            g[i] = g[i + 1] + nums[i + 1];
//
//        for (int i = 0; i < size; i++)
//            if (f[i] == g[i])
//                return i;
//
//        return -1;
//    }
//};
//
//class Solution {
//public:
//    vector<int> productExceptSelf(vector<int>& nums) {
//        int n = nums.size();
//        vector<int> f(n), g(n), answer;
//
//        f[0] = 1;
//        g[n - 1] = 1;
//        for (int i = 1; i < n; i++)
//            f[i] = f[i - 1] * nums[i - 1];
//
//        for (int i = n - 2; i >= 0; i--)
//            g[i] = g[i + 1] * nums[i + 1];
//
//        for (int i = 0; i < n; i++)
//            answer.push_back(f[i] * g[i]);
//
//        return answer;
//    }
//};
#include<unordered_map>
//class Solution {
//public:
//    int subarraySum(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        hash[0] = 1;
//
//        int sum = 0, ret = 0;
//        for (auto x : nums)
//        {
//            sum += x;
//            if (hash.count(sum - k)) ret += hash[sum - k];
//            hash[sum]++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int subarraysDivByK(vector<int>& nums, int k) {
//        unordered_map<int, int> hash;
//        hash[0] = 1;
//
//        int sum = 0, ret = 0;
//        for (auto x : nums)
//        {
//            sum += x;
//            int r = (sum % k + k) % k;
//            if (hash.count(r)) ret += hash[r];
//            hash[r]++;
//        }
//        return ret;
//    }
//};

//class Solution {
//public:
//    int findMaxLength(vector<int>& nums) {
//        unordered_map<int, int> hash;
//        hash[0] = -1;
//
//        int sum = 0, ret = 0;
//        for (int i = 0; i < nums.size(); i++)
//        {
//            sum += nums[i] == 0 ? -1 : 1;
//            if (hash.count(sum)) ret = max(ret, i - hash[sum]);
//            else hash[sum] = i;
//        }
//        return ret;
//    }
//};


//class Solution {
//public:
//    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
//        //1.初始化前缀和矩阵
//        int m = mat.size(), n = mat[0].size();
//        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
//
//        for (int i = 1; i <= m; i++)
//            for (int j = 1; j <= n; j++)
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];//-1是为了处理下标映射关系，dp多开了空间
//
//        //2.使用
//        vector<vector<int>> ret(m, vector<int>(n));
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//            {
//                //+1是为了处理下标映射关系，dp多开了空间，要与mat和ret相对应
//                int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
//                int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
//                ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
//            }
//        return ret;
//    }
//};
//void Test()
//{
//	int i = 1;
//	// 隐式类型转换
//	double d = i;
//	printf("%d, %.2f\n", i, d);
//	int* p = &i;
//	// 显示的强制类型转换
//	int address = (int)p;
//	printf("%x, %d\n", p, address);
//}

//int main()
//{
//	double d = 12.34;
//	int a = static_cast<int>(d);
//	cout << a << endl;
//
//	int* p = &a;
//	// int address = static_cast<int>(p); //error
//	return 0;
//}
//
//int main()
//{
//	int a = 10;
//	int* p = &a;
//	int address = reinterpret_cast<int>(p);
//	cout << address << endl;
//	return 0;
//}

//int main()
//{
//	double d = 12.34;
//	int a = static_cast<int>(d);
//	cout << a << endl;
//	// 这里使用static_cast会报错，应该使用reinterpret_cast
//	//int *p = static_cast<int*>(a);
//	int* p = reinterpret_cast<int*>(a);
//	return 0;
//}

//void Test()
//{
//    const int a = 2;
//    int* p = const_cast<int*>(&a);
//    *p = 3; //去除了const属性，可以修改
//    cout << a << endl; //2  为什么？
//    cout << *p << endl; //3
//}

//void Test()
//{
//    volatile const int a = 2;
//    int* p = const_cast<int*>(&a);
//    *p = 3; //去除了const属性，可以修改
//    cout << a << endl; //3  
//    cout << *p << endl; //3
//}
//int main()
//{
//    Test();
//    return 0;
//}

//class A
//{
//public:
//	virtual void f()
//	{}
//};
//class B : public A
//{};
//void func(A* pa)
//{
//	B* pb1 = (B*)pa;               //不安全
//	B* pb2 = dynamic_cast<B*>(pa); //安全
//
//	cout << "pb1: " << pb1 << endl;
//	cout << "pb2: " << pb2 << endl;
//}
//int main()
//{
//	A a;
//	B b;
//	func(&a); //父类地址
//	func(&b); //子类地址
//	return 0;
//}

//#include <iostream>
//#include<fstream>
//using namespace std;
////以二进制的形式对文件进行写入
//void WriteBinary()
//{
//	//ofstream ofile; //定义文件流对象
//	//ofile.open("test.bin", ofstream::out | ofstream::binary); //以二进制写入的方式打开test.bin文件
//	ofstream ofile("test.bin", ofstream::out | ofstream::binary); //直接构造也可以
//	char data[] = "fan";
//	ofile.write(data, strlen(data)); //将data字符串写入文件
//	ofile.put('!'); //将字符'!'写入文件
//	ofile.close(); //关闭文件
//}
//
////以二进制的形式对文件进行读取
//void ReadBinary()
//{
//	//ifstream ifile; //定义文件流对象
//	//ifile.open("test.bin", ofstream::in | ofstream::binary); //以二进制读取的方式打开test.bin文件
//	ifstream ifile("test.bin", ofstream::in | ofstream::binary); //直接构造也可以
//	ifile.seekg(0, ifile.end); //跳转到文件末尾
//	int length = ifile.tellg(); //获取当前字符在文件当中的位置，即文件的字符总数
//	ifile.seekg(0, ifile.beg); //重新回到文件开头
//	char data[1024];
//	ifile.read(data, length); //将文件当中的数据全部读取到字符串data当中
//	ifile.close(); //关闭文件
//}
//
////以文本的形式对文件进行写入
//void WriteTxt()
//{
//	//ofstream ofile; //定义文件流对象
//	//ofile.open("test.txt"); //以写入的方式打开test.txt文件
//	ofstream ofile("test.txt");//直接构造也可以
//	char data[] = "fan";
//	ofile.write(data, strlen(data)); //将data字符串写入文件
//	ofile.put('!'); //将字符'!'写入文件
//	ofile.close(); //关闭文件
//}
//
////以文本的形式对文件进行读取
//void ReadTxt()
//{
//	//ifstream ifile; //定义文件流对象
//	//ifile.open("test.txt"); //以读取的方式打开test.txt文件
//	ifstream ifile("test.txt");//直接构造也可以
//	ifile.seekg(0, ifile.end); //跳转到文件末尾
//	int length = ifile.tellg(); //获取当前字符在文件当中的位置，即文件的字符总数
//	ifile.seekg(0, ifile.beg); //重新回到文件开头
//	char data[1024];
//	ifile.read(data, length); //将文件当中的数据全部读取到字符串data当中
//	cout << length << endl;
//	cout << data << endl;
//	ifile.close(); //关闭文件
//}
//
////对文件进行写入操作
//void WriteFile()
//{
//	ofstream ofs("data.txt"); //定义文件流对象，并打开文件
//	ofs << "fan!"; //字符串“流入”文件
//	ofs.close(); //关闭文件
//}
//
////对文件进行读取操作
//void ReadFile()
//{
//	ifstream ifs("data.txt"); //定义文件流对象，并打开文件
//	char data[1024];
//	ifs >> data; //文件数据“流入”字符串data
//	ifs.close(); //关闭文件
//}
//
//int main()
//{
//	WriteBinary();
//	return 0;
//}
//

//class Solution {
//public:
//    void sortColors(vector<int>& nums) {
//        int n = nums.size();
//        int left = -1, right = n, i = 0;
//        while (i < right)
//        {
//            if (nums[i] == 0) swap(nums[++left], nums[i++]);
//            else if (nums[i] == 1) i++;
//            else swap(nums[--right], nums[i]);
//        }
//    }
//};

class Solution {
public:
    int minNumberOfFrogs(string croakOfFrogs) {
        string s = "croak";
        int n = s.size();
        vector<int> hash(n);

        unordered_map<char, int> index;
        for (int i = 0; i < n; i++) index[s[i]] = i;

        for (auto ch : croakOfFrogs)
        {
            if (ch == 'c')
            {
                if (hash[n - 1] != 0) hash[n - 1]--;
                hash[0]++;
            }
            else
            {
                int i = index[ch];
                if (hash[i - 1] == 0) return -1;
                hash[i - 1]--;
                hash[i]++;
            }
        }
        for (int i = 0; i < n - 1; i++)
        {
            if (hash[i] != 0) return -1;
        }
        return hash[n - 1];
    }
};

